The present invention relates generally to object oriented computer software, and more specifically to data structures and runtime methods for minimizing stack storage requirements while supporting exception handling in a Java™ virtual machine implemented in resource-constrained devices such as smart cards and the like.
A virtual machine is an abstract computing machine generated by a software application or sequence of instructions which is executed by a processor. Programs executed on a virtual machine can be architecture-neutral. The term “architecture-neutral” refers to programs, such as those written in the Java™ programming language, which can be executed by a virtual machine on a variety of computer platforms having a variety of different computer architectures. Thus, for example, a virtual machine implemented on a Windows™-based personal computer system will use the same set of instructions as a virtual machine implemented on a UNIX™-based computer system. The result of the platform-independent coding of a virtual machine's sequence of instructions is a stream of one or more bytecodes, each of which is, for example, a one-byte long numerical code.
The Java programming language is an object-oriented programming language. In an object-oriented system, a “class” describes a collection of data and methods that operate on that data. Taken together, the data and methods describe the state of and behavior of an object.
The Java programming language also is verifiable, which means that, prior to execution of an application written in the Java programming language, a determination can be made as to whether any instruction sequence in the program will attempt to process data of an improper type for that bytecode or whether execution of bytecode instructions in the program will cause underflow or overflow of an operand stack.
A Java virtual machine executes virtual machine code written in the Java programming language and satisfies “The Java™ Virtual Machine Specification”, cited below. A Java virtual machine is designed for use with a 32-bit architecture. However, various resource-constrained devices, such as smart cards, have an 8-bit or 16-bit architecture.
Smart cards, also known as intelligent portable data-carrying cards, generally are made of plastic or metal and have an electronic chip that includes an embedded microprocessor to execute programs and memory to store programs and data. Such devices, which can be about the size of a credit card, typically have limited memory capacity. The limited architecture and memory make it impractical or impossible to implement a Java virtual machine on the device. For example, some smart cards have less than 1K of random access memory (RAM) and 16K of read only memory (ROM). An example of a difficulty when implementing a Java virtual machine on a resource-constrained device arises in the handling of exceptions
Referring to FIG. 1, in the context of computer programs written in the Java programming language, an exception handier 100 is a procedure (or a set of instructions within a procedure) that protects a specified set of program code, called a protected code block 102. When a Java program violates the semantic constraints of the Java programming language, the Java virtual machine signals this error to the program as an exception. The exception handler is executed whenever the applicable exception is “thrown” during execution of the corresponding protected code. The Java programming language specification states that an exception will be thrown when semantic constraints are violated and will cause a non-local transfer of control from the point where the exception occurred to a point that can be specified by the programmer. An exception is said to be thrown from the point where it occurred and is said to be caught at the point to which control is transferred. For instance, a particular exception handler, such as a procedure for handling “end-of-file” I/O errors, may be defined to be applicable to a particular portion of a first method 104. If the corresponding exception (i.e., an end-of-file exception in this example) results during execution of the protected code 102, execution of the exception handler 100 is initiated. Exceptions may be thrown implicitly or explicitly. Implicit exceptions are thrown by a Java virtual machine as a result of the execution of a program instruction, such as a null-pointer exception. Alternatively, an explicit exception is included within the body of a method using a Java “throw” statement.
A thrown exception is said to be caught by an exception handler if there is an applicable enclosing exception handler for the thrown exception. An enclosing exception handler is one whose scope or range of applicable instructions includes the instruction that throws a corresponding exception. From the perspective of a particular instruction in a method, the set of enclosing exception handlers is the set of exception handlers whose range of applicable instructions (set of protected code), includes the particular instruction.
The Java programming language often refers to “try statements”, “try blocks”, “catch clauses” and “finally clauses” when referencing exception handlers. A try statement includes a try block, zero or more catch clauses and an optional finally clause. Exceptions are caught by enclosing code in try blocks. A try block is a portion of code to which a particular exception handler applies (i.e., the protected code block). A catch clause defines an exception handler. A finally clause of a try statement provides a mechanism for executing a section of code whether or not an exception is thrown. In a Java program, a statement or expression is dynamically enclosed by a catch clause if it appears within the try block of the try statement of which the catch clause is a part, or if the caller of the statement or expression is dynamically enclosed by the catch clause.
Whether a particular catch clause handles an exception is determined by comparing the class of the exception object that was thrown to the declared type of the parameter of the catch clause. The catch clause handles the exception if the type of its parameter is the class of the exception or a superclass of the class of the exception. Equivalently, a catch clause will catch any exception object that is an instance of the declared parameter type.
If the protected portion of the first method includes calls (called “invoke” instructions in The Java Virtual Machine Specification, referenced below) to other methods 106, which in turn may include nested calls to a set of further methods 108, 110, then end-of-file errors generated by any of the methods 106, 108, 110 called directly or indirectly by the protected code 102 also will cause execution of exception handler 100 to be invoked. However, nested method 112 can include its own end-of-file exception handler 114. If an exception is thrown when executing method 112, then exception handler 114 will be used to handle end-of-file exceptions caused by execution of instructions included in that particular nested method, as well as end-of-file exceptions caused by execution of any methods 116 called by nested method 112.
In conventional Java programs, all the methods associated with an object class are stored together in a data structure called a class file, which is defined in The Java Virtual Machine Specification. Each method has its own exception table and furthermore the code of each method includes the code for the exception handlers referenced by its exception table. When a Java class file is created, all the exceptions associated with a method are arranged in a list, referred to as an exception handler table. Referring to FIG. 2, a conventional exception handler table 200 includes one or more catch clauses (exception handlers) 202. Each catch clause 202 includes a start pc address 204 and stop pc address 206 that describes the Java virtual machine instruction range for which the exception handler is active, a type indicator 208 that describes the types of exceptions that the catch clause is to handle, and an address 210 at which execution of the exception handler code is to begin.
The order of the catch clauses in the exception handler table is important. The throwing of an exception results in a search by the Java virtual machine through the exception handler table. The Java virtual machine execution continues at a first matching catch clause. Because Java code is structured, it is always possible to arrange all the exception handlers for one method in a single list. For any possible program counter value, this list can be searched to find the proper exception handler, that is, the innermost exception handler that both encloses the program counter (pc) value (where the exception was thrown) and can handle the exception being thrown.
If there is no matching catch clause, the current method is said to have an uncaught exception. When an exception is uncaught, the execution state of the invoker, the method that invoked the current method (if any), is restored. The propagation of the exception continues as though the exception had occurred in the invoker at the instruction that invoked the method actually raising the exception.
Various runtime data structures are maintained by a Java virtual machine to keep track of the execution and invocation of methods. A Java virtual machine can support many threads of execution at once. Each Java virtual machine thread has its own pc (program counter) register. The pc register contains the address of the Java virtual machine instruction currently being executed. Each Java virtual machine thread has a private Java stack, created at the same time as the thread. The Java stack stores Java virtual machine frames. The Java stack is equivalent to the stack of a conventional language such as C: it holds local variables and partial results, and supports method invocation and return.
Referring now to FIG. 3, a conventional Java stack 300 including a plurality of Java virtual machine frames 302 is shown. Each frame 302 includes a reference 304 to a method and a return pointer 306.
Reference 304 is a reference to the method that is currently executing, referred to as the current method. Reference 304 is used to indicate which exception handler table to search when an exception is thrown during the execution of the current method. Reference 304 may be of the form of an address at which the current method is stored. The code for each method typically includes the maximum stack space needed by the method, the maximum number of registers used by the method, the actual bytecodes for executing the method and a table of exception handlers. Reference 304 can point to the beginning of the current method where the exception handler table is typically stored.
Return pointer 306 is a pointer to the method that invoked the current method, and more specifically to the location where execution is to resume in the invoking method at the completion of execution of the current method.
As described above, smart cards and other resource-constrained devices typically include limited memory capacity. Accordingly, programs including a plurality of nested methods that require plural bytes to be stored on the Java stack may cause a stack overflow condition at runtime. It is desirable to limit the information required to be stored in memory at runtime while allowing full support for conventional exception handling in a Java virtual machine.